Lossless compression algorithms do not deliver compression ratios that are high enough for most broadcast and internet transmission applications. As a result, most multimedia compression algorithms are lossy. Lossy compression yields a much higher compression ratio than that of lossless compression owing to the fact that the compressed data is not the same as the original data, but a close approximation of it. With a relatively conservative compression ratio, the compressed data and the original can appear to be the perceptually indistinguishable. Known implementations of lossy compression algorithms include JPEG, JPEG2000, DPCM, MPEG1, MPEG2, MPEG4 and others.
Integer transforms have been widely used in the latest video coding standards, such as H.264, VC-1, and Audio Video Standard (AVS) as the corresponding data sizes involved do not permit a lossless compression method.
Known implementations of video coding methods have been documented including “High-definition Video Coding with Super-macroblocks,” Siwei Ma and C.-C. Jay Kuo; Proc. of SPIE-IS&T Electronic Imaging, SPIE Vol. 6508, 650816, Visual Communications and Image Processing 2007. While a complex transform is mentioned, the disclosed transform has a low the energy-packing ability and as such suffers from performance limitations.
Another implementation is described in “A Universal Approach to Developing Fast Algorithm for Simplified Order-16 ICT,” Jie Dong; King Ngi Ngan; Chi Keung Fong; Wai Kuen Cham; IEEE International Symposium on Circuits and Systems, 2007. ISCAS 2007. 27-30 May 2007 Page(s): 281-284. A similar implementation is also disclosed in “An order-16 integer cosine transform,” Cham, W. K.; Chan, Y. T.; IEEE Transactions on Signal Processing, Volume 39, Issue 5, May 1991 Page(s): 1205-1208. Transforms mentioned in above two papers are complex and as such suffer from restrictions on when they would be suitably implemented and as such do not offer the best balance between their complexity and respective energy-packing ability.
Integer transforms of video coding in the prior art have mainly focused on the creation of integer transform matrices. U.S. Patent Publication No. 20030156648 entitled “Sub-block transform coding of prediction residuals” employs a closed loop evaluation of the different transform sizes and switching levels but describes a predictive system rather than a system optimized for a particular order transform.
In addition, U.S. Patent Publication No. 20070223590 discloses a method which reduces computational complexity of integer transforms. The method uses a 2N×2N integer transform matrix. Similarly, United States Patent Application 20040062309 entitled “Method for transformation-coding full motion image sequences” in which motion vectors are estimated block-by-block, with which said motion vectors motion compensation is carried out, but the disclosed method is distinguishable from the claimed invention as it is does not undertake the claimed transform.